import java.util.PriorityQueue;

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> heap = new PriorityQueue<>((v1, v2) -> v1.val - v2.val);

        for (ListNode node: lists) {
            if (node != null) heap.offer(node);
        }

        ListNode ret = new ListNode();
        ListNode prev = ret;
        while (!heap.isEmpty()) {
            ListNode t = heap.poll();
            prev.next = t;
            prev = t;
            if (t.next != null) heap.offer(t.next);
        }
        return ret.next;
    }
}